package codetop.microsoft.T402;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: 18362
 * @Create: 2022-09-07 23:28:18 星期三
 */
class Solution {
    public String removeKdigits(String num, int k) {
        if (k == num.length())
            return "0";
        StringBuilder sb = new StringBuilder();
        Deque<Character> dq = new LinkedList<>();
        int i = 0, cnt = num.length() - k;
        while (k > 0 && i < num.length()) {
            while (!dq.isEmpty() && k>0 && dq.getLast() > num.charAt(i)) {
                k--;
                dq.removeLast();
            }
            dq.addLast(num.charAt(i++));
        }
        while (i < num.length())
            dq.addLast(num.charAt(i++));
        int t = 0;
        while (!dq.isEmpty() && t < cnt) {
            char c = dq.removeFirst();
            if (sb.length() > 0 || c != '0')
                sb.append(c);
            t++;
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}